package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/combinations/">组合(Combinations)</a>
 * <p>给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。</p>
 * <p>你可以按 任何顺序 返回答案。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：n = 4, k = 2
 *      输出：
 *      [
 *        [2,4],
 *        [3,4],
 *        [2,3],
 *        [1,2],
 *        [1,3],
 *        [1,4],
 *      ]
 *
 *  示例 2：
 *      输入：n = 1, k = 1
 *      输出：[[1]]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= n <= 20</li>
 *     <li>1 <= k <= n</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/12 10:34
 */
public class LC0077Combinations_M {
    static class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> resList = new ArrayList<>();
            backtracking(n, k, 1, new ArrayList<>(), resList);
            //backtracking2(n, k, 1, new ArrayList<>(), resList);
            return resList;
        }

        private void backtracking(int n, int k, int startIdx, List<Integer> path, List<List<Integer>> resList) {
            if (path.size() == k) {                     // 终止条件
                resList.add(new ArrayList<>(path));     // 存放结果
                return;                                 // return
            }
            // i <= n - (k - path.size()) + 1：如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
            for (int i = startIdx; i <= n - (k - path.size()) + 1; i++) {
                path.add(i);                                        // 处理节点
                backtracking(n, k, i + 1, path, resList);   // 递归
                path.remove(path.size() - 1);   // 回溯，撤销处理结果
            }
        }

        private void backtracking2(int n, int k, int startIdx, List<Integer> path, List<List<Integer>> resList) {
            if (k == 0) {
                resList.add(new ArrayList<>(path));
                return;
            }
            for (int i = startIdx; i <= n - k + 1; i++) {
                path.add(i);
                backtracking2(n, k - 1, i + 1, path, resList);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListListInteger(solution.combine(4, 2));
        Printer.printListListInteger(solution.combine(1, 1));
    }
}
